#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Nodo{
    int dato;
    struct Nodo *siguiente;
    struct Nodo *anterior;
}Nodo;

typedef struct {
    Nodo *inicio;
} Lista;

void inicializacion (Lista * tas){
    tas->inicio = NULL;
}
int  agregarAlFinal(Lista *tas,int dato){
    Nodo *nuevo_elemento;
    Nodo *actual;

    nuevo_elemento = (Nodo *) malloc (sizeof (Nodo));

    nuevo_elemento->dato= dato;
    nuevo_elemento->siguiente =NULL;


   if(tas->inicio==NULL)
   {
     tas->inicio=nuevo_elemento;
     nuevo_elemento->anterior=NULL;
   }
   else
   {
       actual=tas->inicio;
       while(1)
       {
           if(actual->siguiente==NULL)
           {
               break;
           }
            actual=actual->siguiente;
       }
          actual->siguiente=nuevo_elemento;
          nuevo_elemento->anterior=actual;
   }
}
void agregarAlPricipio(Lista * tas,int dato){
    Nodo *nuevo_elemento;
    nuevo_elemento = (Nodo *) malloc (sizeof (Nodo));
    nuevo_elemento->dato= dato;
    nuevo_elemento->siguiente = tas->inicio;
    tas->inicio = nuevo_elemento;
    if(nuevo_elemento->siguiente!=NULL)
    {
        nuevo_elemento->siguiente->anterior=nuevo_elemento;
    }
}

void muestraLista (Lista * tas){
    Nodo *actual;

    actual = tas->inicio;
    if (actual==NULL) return;
    while(1)
    {
        cout<< actual->dato <<endl;
        if (!actual->siguiente) break;
        actual = actual->siguiente;
    }
}
int agregarOrdenado (Lista *tas, int dato){
    Nodo *nuevo_elemento;
    Nodo *actual;

    nuevo_elemento = (Nodo *) malloc (sizeof (Nodo));

    nuevo_elemento->dato= dato;
   if(tas->inicio==NULL)
   {
     tas->inicio=nuevo_elemento;
      nuevo_elemento->siguiente=NULL;
      nuevo_elemento->anterior=NULL;
   }
   else
   {
       actual=tas->inicio;
       if(actual->dato>nuevo_elemento->dato)
       {
           nuevo_elemento->siguiente = tas->inicio;
           tas->inicio->anterior = nuevo_elemento;
           tas->inicio=nuevo_elemento;
           nuevo_elemento->anterior=NULL;
       }
       else
       {
           while(1)
            {
                if(actual->dato>nuevo_elemento->dato)
                {
                    actual->anterior->siguiente=nuevo_elemento;
                    nuevo_elemento->anterior=actual->anterior;
                    nuevo_elemento->siguiente=actual;
                    actual->anterior=nuevo_elemento;
                    break;
                }
                if(actual->siguiente==NULL)
                {
                    actual->siguiente=nuevo_elemento;
                    nuevo_elemento->anterior=actual;
                    nuevo_elemento->siguiente=NULL;
                    break;
                }
                actual=actual->siguiente;
            }
       }
    }
}
int eliminarPrimero(Lista *tas){
    Nodo *sup_elemento;
    if (tas->inicio==NULL)
        return -1;
    sup_elemento = tas->inicio;
    tas->inicio = tas->inicio->siguiente;
    if(tas->inicio !=NULL)
    {
        tas->inicio->anterior=NULL;
    }
    free (sup_elemento);
    return 0;
}
int eliminarUltimo(Lista *tas){
    Nodo *sup_elemento;
    if (tas->inicio!=NULL)
   {
       sup_elemento = tas->inicio;
       while(1)
       {
           if(sup_elemento->siguiente==NULL)
           {
                if(sup_elemento->anterior!=NULL)
                {
                    sup_elemento->anterior->siguiente=NULL;

                }
                else
                {
                    tas->inicio=NULL;
                }
                free (sup_elemento);
                break;
           }

            sup_elemento = sup_elemento->siguiente;
       }


   }
return 0;
}

void buscarNodo (Lista *tas,int OPNodo){
    Nodo *actual;
   if(tas->inicio!=NULL)
   {
       actual=tas->inicio;
       while(1)
       {
            if(actual->dato==OPNodo)
            {
                cout<<"El Numero que ingreso ("<<OPNodo<<") existe en otro Nodo"<<endl;
                cout<<"*********************************************"<<endl;
                break;
            }
            if(actual->siguiente==NULL)
            {
               break;
            }
            actual=actual->siguiente;
       }

   }
}
void ordenar(Lista *tas,int cantDatos){
    int aux, flag;
    int j,i;
    Nodo *actual;
   if(tas->inicio!=NULL)
   {

       for(j=0; j<cantDatos; j++)
       {
           flag=1;
           actual=tas->inicio;
           for(i=0;i<(cantDatos-1);i++)
           {
               if(actual->dato > actual->siguiente->dato)
               {
                   flag=0;
                   aux=actual->dato;
                   actual->dato=actual->siguiente->dato;
                   actual->siguiente->dato=aux;
               }
                actual=actual->siguiente;
           }
           if(flag==1)
           {
               break;
           }
       }
   }
}
int main()
{
    Lista *tas;
    int  nom;
    int op;
    int OPNodo;
    int cantDatos=0;

    if ((tas = (Lista *) malloc (sizeof (Lista))) == NULL)
        return -1;
    inicializacion (tas);
    while(1)
    {
        cout<<"MENU........................"<<endl;
        cout<<"1-Agregar al Final"<<endl;
        cout<<"2-Agregar al Principio"<<endl;
        cout<<"3-Agregar Ordenado"<<endl;
        cout<<"4-Eliminar Ultimo"<<endl;
        cout<<"5-ELiminar Primero"<<endl;
        cout<<"6-Buscar Nodo(Dato)"<<endl;
        cout<<"7-Ordenar"<<endl;
        cout<<"8-Mostrar Lista"<<endl;
        cout<<"9-Salir"<<endl;
        cout<<endl;
        cout<<"Elegir opcion: ";
        cin>>op;
        cout<<"----------------------------------------------"<<endl;
        if(op==1 || op==2 || op==3)
        {
            cout<<"Ingrese un Numero: ";
            cin>>nom;
        }
        switch(op)
        {
            case 1:
            agregarAlFinal(tas,nom);
            cantDatos++;
            cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 2:
            agregarAlPricipio(tas,nom);
            cantDatos++;
            cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 3:
            agregarOrdenado(tas,nom);
            cantDatos++;
            cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 4:
            eliminarUltimo(tas);
            cantDatos--;
            cout<<"Eliminacion del Ultimo Dato"<<endl;
            cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 5:
            eliminarPrimero(tas);
            cantDatos--;
            cout<<"Eliminacion del Primer Dato"<<endl;
             cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 6:
            cout<<"Ingrese el valor que desea buscar: "<<endl;
            cin>>OPNodo;
            buscarNodo(tas,OPNodo);
            break;
            case 7:
            ordenar(tas,cantDatos);
            cout<<endl<<"********** Comienzo de Cola **********"<<endl;
            muestraLista(tas);
            cout<<endl<<"**********    Fin de Cola   **********"<<endl<<endl;
            break;
            case 8:
            muestraLista(tas);
            break;
            case 9:
            return 1;
            break;
        }
    }
    return 1;
}

